/**
 * 电话号码的字母组合
 *
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 * 示例 1：
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 *
 * 示例 2：
 * 输入：digits = ""
 * 输出：[]
 *
 * 示例 3：
 * 输入：digits = "2"
 * 输出：["a","b","c"]
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 本题的思路就是要找出得到电话的所有字母组合, 担责花姑娘长的循环, 会让我们摸不着头脑, 因为我们面临这两个问题需要解决,
 * 1. 我们需要带到对应数字映射的字母, 这映射的字母可不止一个, 我们徐亚哦对他第一次循环,
 * 2. 我们需要知道后面还剩下数字个数, 并且他们所对的字母还是不止一个, 我们不仅要在循环这些剩下的数字的同时, 还要循环处理这些数字对应的字母
 * .... 这无疑是特别困难的
 * 到我们观察题目给出的答案, 可以看到, 都是先第一个数字对应的字母开始组合, 后面在一个一个后面的数字对应的字母开始组合, 这有点给我们可以用递归的感觉
 * 想到就开始写
 * 首先我们需要定义一些用于全局的变量, 比如用于映射字母的字符串数组....
 * 在循环体中我们需要将每个字母添加到字符串组合函数上, 然后在递归处理后面的字符, 当然这个操作第一个数字所对应的字母都需要做一次, 也就是需要再循环体
 * 中进行
 * 然后进入下一层循环, 这时候我们会发现我们需要上次得到的字母组合, 于是我们需要将字母组合一同传递过来
 * 当我们的递归进行到最后一个数字的时候就需要将字母组合加进所要返回的 list中了
 * 处理好这些后, 我们在出循环的时候还要将之前对应的下标还原, 不急你要还原下标还要还字符串组合函数
 */

public class Main {

    // 定义全局变量, 以便于后面的函数好调用
    // 下标映射字符串
    String[] s = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    // 返回的 list集合
    List<String> ret;

    // str对应的数字的位数
    int n;

    // 按顺序存储每一位数字
    int[] nums;

    public List<String> letterCombinations(String str) {

        // 初始化
        ret = new ArrayList<>();

        // 求长度
        n = str.length();

        // 注意, 要是长度为 0 , 要返回空 list
        if (n == 0) {
            return ret;
        }

        // 初始化
        nums = new int[n];

        // 存储每一位数字
        for (int i = 0; i < n; i++) {

            // 得到的字符 , 需要减去对应的 '0' 才能转化为对应的数字
            nums[i] = str.charAt(i) - '0';
        }

        // 字符串拼接函数
        StringBuffer tmp = new StringBuffer();

        // 深度遍历函数, 传入一开始对应的下标 0
        dfs(0, tmp);

        // 返回结果
        return ret;
    }


    /**
     * 深度优先遍历
     *
     * @param i   : 所对应的数字下标
     * @param tmp : 上次的字符组合
     */
    private void dfs(int i, StringBuffer tmp) {

        // 如果超出数字位数, 添加结果, 并记得 return终止循环
        if (i == n) {
            ret.add(tmp.toString());
            return;
        }

        // 求出这个数字所对应的字母
        String ss = s[nums[i]];

        // 求字母个数
        int m = ss.length();

        // 遍历每个字母
        for (int j = 0; j < m; j++) {

            // 添加这次字母
            tmp.append(ss.charAt(j));

            // 开始深度优先遍历
            dfs(++i ,tmp);

            // 出来记得恢复现场
            // 要回复的有两个

            // 恢复下标
            i--;

            // 恢复字母组合
            tmp.deleteCharAt(tmp.length() - 1);
        }

    }
}